//合并排序链表
class Solution {
public:
    //思路 ： 每个链表都是有序的 那么就将这几个有序的链表再次进行排序选大小
    //使用优先级队列进行排序 如果某一个节点是当前比较元素中的最小值
    //把这个节点pop掉 将其后续节点push进来
    struct cmp
    {
        bool operator()(ListNode* a,ListNode* b)
        {
            return a->val>b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        if(lists.size()==0) return nullptr;
        priority_queue<ListNode*,vector<ListNode*>,cmp> q;
        for(auto node:lists)
        {
            if(node)
            q.push(node);
        }
        ListNode* phead= new ListNode(-1);
        ListNode* cur=phead;
        while(!q.empty())
        {
            ListNode* top=q.top();
            q.pop();
            cur->next=top;
            cur=cur->next;
            if(top->next) q.push(top->next);
        }
        return phead->next;
    }
};
//所有子集
class Solution {
public:
    vector<vector<int>> res;
    vector<int>tmp;
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        int n=nums.size();
        used.resize(n,false);
        dfs(nums,0);
        return res;
    }
    void dfs(vector<int>& nums,int index)
    {
        res.push_back(tmp);
        for(int i=index;i<nums.size();i++)
        {
                used[i]=true;
                tmp.push_back(nums[i]);
                dfs(nums,i+1);
                used[i]=false;
                tmp.pop_back();
        }
    }
};
//含有K个元素的组合
class Solution {
public:
    vector<int>tmp;
    vector<vector<int>>res;
    vector<vector<int>> combine(int n, int k) 
    {
        dfs(1,k,n);
        return res;
    }
    void dfs(int index,int k,int n)
    {
        if(tmp.size()==k)
        {
            res.push_back(tmp);
        }
        for(int i=index;i<=n;i++)
        {
            tmp.push_back(i);
            dfs(i+1,k,n);
            tmp.pop_back();
        }
    }
};
//开幕式烟火
class Solution {
public:
    set<int> m;
    int numColor(TreeNode* root) 
    {
        if(!root) return 0;
        preorder(root);
        return m.size();
    }
    void preorder(TreeNode* root)
    {
        if(!root) return ;
        if(m.count(root->val)==0)
        {
            m.insert(root->val);
        }
        preorder(root->left);
        preorder(root->right);
    }
};
//一次编辑
class Solution {
public:
    bool oneEditAway(string first, string second) 
    {
        int m=first.size();
        int n=second.size();
        if(m-n>1 || n-m >1) return false;
        if(m<n)
        {
            return oneEditAway(second,first);
        }
        int i=0,j=0;
        int diff=0;
        while(i<m && j<n)
        {
            if(first[i]==second[j])
            {
                i++;j++;
            }
            else
            {
                diff++;
                if(diff>1) return false;
                if(m>n) i++;
                else
                {
                    i++;
                    j++;
                }
            }
        }
        return true;
    }
};
//分割链表
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        //思路: 由于链表的遍历只能O(n)
        //所以我们可以选择创建两个链表 以x值为分界 将两种条件的节点
        //分别挂在不同的链表上最后将这两个链表合并
        ListNode* low=new ListNode(-1);
        ListNode* high=new ListNode(-1);
        ListNode* p1=low,*p2=high;
        while(head)
        {
            if(head->val<x) 
            {
                p1->next=head;
                p1=p1->next;
            }
            else
            {
                p2->next=head;
                p2=p2->next;
            }
            head=head->next;
        }
        p2->next=nullptr;
        p1->next=high->next;
        return low->next;
    }
};
//求和路径
class Solution {
public:
    int pathSum(TreeNode* root, int sum) 
    {
        if(!root) return 0;
        int res=0;
        res+=dfs(root,sum);
        res+=pathSum(root->left,sum);
        res+=pathSum(root->right,sum);
        return res;
    }
    int dfs(TreeNode* root,int sum)
    {
        if(!root) return 0;
        int res=0;
        if(root->val==sum) res++;
        res+=dfs(root->left,sum-root->val);
        res+=dfs(root->right,sum-root->val);
        return res;
    }
};